package com.leetcode.www;

import java.util.ArrayList;
import java.util.List;

/**
 * Creared with IntelliJ IDEA.
 * Description:给你一个 无重复元素 的整数数组candidates 和一个目标整数target，找出candidates中可以使数字和为目标数target 的 所有不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。
 *
 * candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。
 *
 * 对于给定的输入，保证和为target 的不同组合数少于 150 个。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/combination-sum
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * User:yxd
 * Date:2022-03-17
 * Time:12:01
 */
public class DFS39 {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> ret = new ArrayList<>();
        if(candidates == null)return ret;
        List<Integer> list = new ArrayList<>();
        DFS(candidates,0,ret,list,0,target);
        return ret;
    }
    public void DFS(int[] candidates,int index,List<List<Integer>> ret,List<Integer> list,int sum,int target){
        if(sum >= target){
            if(sum == target){
                ret.add(new ArrayList<>(list));
            }
            return;
        }
        for(int i = index;i < candidates.length;i ++){//可以重复使用
            if(candidates[i] > target){
                continue;
            }
            list.add(candidates[i]);
            DFS(candidates,i,ret,list,sum + candidates[i],target);//每次加上当前的数字直至和超过或者等于所求和为止,此时的i不用加一
            list.remove(list.size() - 1);//回溯
        }

    }
}
